# -*- coding: utf-8 -*-

"""剑指 Offer II 116. 省份数量
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。

示例 1：
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2：
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

提示：
1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]"""

from queue import Queue

class Solution:
    """维护一个所有城市的集合
    从这个集合中随便拿处一个城市，做宽度优先遍历，没遍历到一个城市，就从集合中删点，直到将这个子图全部遍历完，算一个省份
    重复上述步骤，直到集合中没有城市，则所有省份圈闭完成。
    
    直接用索引来代表城市，用一个数组来表示城市集合，这个城市还没有省份归属置1，已经被遍历到则置0"""
    def findCircleNum(self, isConnected: list) -> int:
        size = len(isConnected)
        cities = [1 for _ in range(size)]

        prov_count = 0
        while True:
            try:
                city = cities.index(1)    # 开始一个新的省份

                que = Queue()
                que.put(city)
                visited = set()
                while not que.empty():
                    city = que.get()

                    cities[city] = 0
                    visited.add(city)

                    tocity = 0
                    while tocity < size:
                        if (tocity not in visited) and (isConnected[city][tocity] == 1):
                            que.put(tocity)
                        tocity += 1

            except ValueError:
                break
            else:
                prov_count += 1

        return prov_count

if __name__ == '__main__':
    print(Solution().findCircleNum(isConnected = [[1,1,0],[1,1,0],[0,0,1]]))
    print(Solution().findCircleNum(isConnected = [[1,0,0],[0,1,0],[0,0,1]]))
